题目描述
给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1:
plaintext
1 | 输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 |
示例 2:
plaintext
1 | 输入:root = [1,2,3], targetSum = 5 |
示例 3:
plaintext
1 | 输入:root = [1,2], targetSum = 0 |
提示:
- 树中节点总数在范围 [0,5000] 内
- −1000<=Node.val<=1000
- −1000<=targetSum<=1000
注意:本题与主站 113 题相同:https://leetcode-cn.com/problems/path-sum-ii/
算法
(递归,前序遍历) O(n)
使用前序遍历的顺序遍历二叉树,遍历一个节点将其加入到路径数组 path 中,如果当前节点是叶子节点且路径和 sum+root−>val=target,则说明在树中找到了一条满足路径,将当前路径加入到答案中,继续递归处理左子树和右子树,最后不要忘了 path 数组回溯。
时间复杂度
O(n)
空间复杂度
最坏情况下,叶子节点的个数为 O(2n−1),其中 n 是二叉树的层数,每个叶子节点对应一个方案,每个方案上的节点个数是 n,所以总时间复杂度为 O(n∗2n−1)
C++ 代码
cpp
1 | /** |